import javax.print.event.PrintEvent;
import java.util.ArrayList;

public class nums {
    /**
     * 一个整型数组中除了两个数字之外,其他数字都出现了两次,请写程序找出这两个只出现一次的数字
     * 思路:
     * 1.如果只有一个数据单独出现,整体异或得到结果
     * 但是这道题是两个不重复的数据,我们可以采取先整体异或,异或结果一定不为0,而其中为1的比特位,不同的两个数据该
     * 位置上的数据一定不同,所以我们可以用该比特位进行分组
     * 分组的结果一定是,相同数据被分到了一组,不同的数据一定被分到了不同的组
     * 相同数据异或,就是0
     * 任何数和0异或,就是他本身
     */
    public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
        if(array == null || num1 == null || num2 == null) {
            return;
        }
        int result = array[0];
        //第一步,整体异或
        for (int i = 1; i < array.length; i++) {
            result ^= array[i];
        }
        //第二步,根据题意,最终结果一定不为0,找到该数据第一个为1的比特位,从高到低
        int size = Integer.SIZE;//获取int有多少比特位
        int flag = 1;
        //int i = 0;
        while (size >= 0) {
            size -= 1;
            if (((flag << size) & result )!= 0) {
                flag <<= size;
                break;
            }
            //i++;
            //size--;
        }
        num1[0] = 0;
        num2[0] = 0;
        //第三步 分组
        for (int i = 0; i < array.length; i++) {
            if ((array[i] & flag) == 0) {
                num1[0] ^= array[i];//再次异或
            }else {
                num2[0] ^= array[i];//再次异或
            }
        }

    }
    /**
     * 输出所有和为s的连续正数序列.序列内按照从小至大的顺序,序列按照开始数字从小到大的顺序
     * 滑动窗口
     */
    public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        //不考虑负数情况
        //定义两个位置,表示起始和结束,start和end之间就是一段连续递增的序列
        //两个起点,相当于滑动窗口的两边,根据其窗口内的值的和来确定窗口位置和大小
        //采用闭区间的方式进行解决
        int low = 1;
        int high = 2;
        while (low < high) {
            //由于这是连续的,差为1的一个序列,那么求和公式是(a0+an)*n/2
            //这里的low和high不光是代表位置,也代表对应的值
            int total = (low + high)*(high-low+1)/2;
            if (total == sum) {
                ArrayList<Integer> list = new ArrayList<>();
                for (int i = low; i <= high; i++) {
                    list.add(i);
                }
                result.add(list);
                low++;
            }else if (total < sum){
                high++;
                //说明该序列区间中的数据和小于sum,应该扩大区间,以包含更多的数据
            }else {
                //说明该序列区间中的数据和大于sum,应该缩小区间,以包含较少数据
                low++;
            }
        }
        return result;
    }

    /**
     * 字符串逆置,循环次数去重
     * 对于给定一个字符序列S,请你把其循环左移K位之后的序列输出,
     * 例如:字符序列S="abcXYZdef",
     * 要求输出左移3位后的结果,即"XYZdefabc"
     * 思路1:保存第一个,剩下的整体前移一个,第一个放在最后,完成一次移动,一次能移动,多次也可以
     * 思路2:局部逆置,再整体逆置
     */
    public String LeftRotateString(String str,int n) {
        if(str.length() <= 0 || n <= 0) {
            return str;
        }
        int step = n % str.length();
        char[] list = str.toCharArray();
        reverse1(list,0,step-1);
        reverse1(list,step,str.length()-1);
        reverse1(list,0,str.length()-1);
        return new String(list);

    }

    private void reverse1(char[] list, int start, int end) {
        while (start < end) {
            char temp = list[start];
            list[start] = list[end];
            list[end] = temp;
            start++;
            end--;

        }
    }
    /**
     * “student. a am I” ==> “I am a student.”
     * 字符串逆置的问题
     */
    public String ReverseSentence(String str) {

        if (str.length() == 0 || str == null) {
            return str;
        }
        char[] list = str.toCharArray();    
        int len = list.length;
        int i = 0;
        int j = i;
        while (i < len) {
            //让 i 一直往后走,碰到第一个空格
            while (i < len && !Character.isSpaceChar(list[i])) i++;
            //逆置当前有效字符串,我们采用闭区间
            Reverse(list,j,i-1);
            //过滤所有空格,指向下一个有效子串的开始
            while (i < len && Character.isSpaceChar(list[i])) i++;
            j = i;//保存起始位置
        }
        //走到这里,一定是i == str.size()了,但是最后一个有效子串并没有被逆置,故逆置
        Reverse(list,j,i-1);
        Reverse(list,0,len-1);
        return new String(list);
    }

    private void Reverse(char[] list, int start, int end) {
        while (start < end) {
            char temp = list[start];
            list[start] = list[end];
            list[end] = temp;
            start++;
            end--;
        }

    }

}
